typedef double (*pf) (double);

double newton(double _x[], pf p, int _n,double x)
{
	double y[50]={0};
	double difference[50][50]={0};
	for (int i = 0; i <= _n; i++) {
		y[i] = p(_x[i]);
	}
	for (int i = 0; i <= _n; i++) {
		difference[i][0] = y[i];
	}
	for (int j = 1; j <= _n; j++) {
		for (int i = j; i <= _n; i++) {
			difference[i][j] = (difference[i][j - 1] - difference[i - 1][j - 1]) / (_x[i] - _x[i - j]);
		}
	}
	double sum = difference[0][0];
	for (int i = 1; i <= _n; i++) {
		double temp = 1;
		for (int j = 0; j < i; j++) {
			temp *= (x - _x[j]);
		}
		sum = sum + difference[i][i] * temp;
	}
	return sum;
}
